\section{Duff's device}
\myindex{Duff's device}

Duff's device 
\footnote{\href{http://go.yurichev.com/17138}{wikipedia}}
это развернутый цикл с возможностью перехода в середину цикла.
Развернутый цикл реализован используя fallthrough-выражение switch().
Мы будем использовать здесь упрощенную версию кода Тома Даффа.
Скажем, нам нужно написать функцию, очищающую регион в памяти.
Кто-то может подумать о простом цикле, очищающем байт за байтом.
Это, очевидно, медленно, так как все современные компьютеры имеют намного более широкую шину памяти.
Так что более правильный способ --- это очищать регион в памяти блоками по 4 или 8 байт.
Так как мы будем работать с 64-битным примером, мы будем очищать память блоками по 8 байт.

Пока всё хорошо.
Но что насчет хвоста? 
Функция очистки памяти будет также вызываться и для блоков с длиной не кратной 8.

Вот алгоритм:

\begin{itemize}
\item вычислить количество 8-байтных блоков, очистить их используя 8-байтный (64-битный) доступ к памяти;

\item вычислить размер хвоста, очистить его используя 1-байтный доступ к памяти.

\end{itemize}

Второй шаг можно реализовать, используя простой цикл.
Но давайте реализуем его используя развернутый цикл:

\lstinputlisting[style=customc]{\CURPATH/duff_RU.c}

В начале разберемся, как происходят вычисления.
Размер региона в памяти приходит в 64-битном значении.
И это значение можно разделить на две части:

% .... 7 6 5 4 3 2 1 0
%|....|B|B|B|B|B|S|S|S|

\begin{center}
\begin{bytefield}[endianness=big,bitwidth=0.03\linewidth]{11}
\bitheader{7,6,5,4,3,2,1,0} \\
\bitbox{3}{\dots} & 
\bitbox{1}{B} & 
\bitbox{1}{B} & 
\bitbox{1}{B} & 
\bitbox{1}{B} & 
\bitbox{1}{B} & 
\bitbox{1}{S} & 
\bitbox{1}{S} & 
\bitbox{1}{S}
\end{bytefield}
\end{center}

( \q{B} это количество 8-байтных блоков и \q{S} это длина хвоста в байтах ).

Если разделить размер входного блока в памяти на 8, то значение просто сдвигается на 3 бита вправо.
Но для вычисления остатка, нам нужно просто изолировать младшие 3 бита!
Так что количество 8-байтных блоков вычисляется как $count>>3$, а остаток как $count \& 7$.
В начале, нужно определить, будем ли мы вообще исполнять 8-байтную процедуру,
так что нам нужно узнать, не больше ли $count$ чем 7.
Мы делаем это очищая младшие 3 бита и сравнивая результат с нулем, потому что,
всё что нам нужно узнать, это ответ на вопрос, содержит ли старшая часть значения $count$ ненулевые биты.
Конечно, это работает потому что 8 это $2^{3}$, так что деление на числа вида $2^n$ это легко.
Это невозможно с другими числами.

А на самом деле, трудно сказать, стоит ли пользоваться такими хакерскими трюками, потому что они
приводят к коду, который затем тяжело читать.

С другой стороны, эти трюки очень популярны и практикующий программист, хотя может и не использовать
их, всё же должен их понимать.

Так что первая часть простая: получить количество 8-байтных блоков и записать 64-битные нулевые значения
в память.

Вторая часть --- это развернутый цикл реализованный как fallthrough-выражение switch().

В начале, выразим на понятном русском языке, что мы хотим сделать.

Мы должны \q{записать столько нулевых байт в память, сколько указано в значении $count\&7$}.

Если это 0, перейти на конец, больше ничего делать не нужно.

Если это 1, перейти на место внутри выражения switch(), где произойдет только одна операция записи.

Если это 2, перейти на другое место, где две операции записи будут исполнены, итд.
7 во входном значении приведет к тому что исполнятся все 7 операций.

8 здесь нет, потому что регион памяти размером в 8 байт будет обработан первой частью нашей функции.

Так что мы сделали развернутый цикл.
Это однозначно работало быстрее обычных циклов на старых компьютерах
(и наоборот, на современных процессорах короткие циклы работают быстрее развернутых).

Может быть, это всё еще может иметь смысл на современных маломощных дешевых \ac{MCU}.

Посмотрим, что сделает оптимизирующий MSVC 2012:

\lstinputlisting[style=customasmx86]{\CURPATH/duff_MSVC2012_x64_Ox_RU.asm}

Первая часть функции выглядит для нас предсказуемо.

Вторая часть --- это просто развернутый цикл и переход передает управление на нужную инструкцию
внутри него.

Между парами инструкций \TT{MOV}/\TT{INC} никакого другого кода нет, так что исполнение
продолжается до самого конца, исполняются столько пар, сколько нужно.

Кстати, мы можем заметить, что пара \TT{MOV}/\TT{INC} занимает какое-то фиксированное количество
байт (3+3).

Так что пара занимает 6 байт.
Зная это, мы можем избавиться от таблицы переходов в switch(), мы можем просто умножить входное значение
на 6 и перейти на \TT{текущий\_RIP + входное\_значение * 6}.

Это будет также быстрее, потому что не нужно будет загружать элемент из таблицы переходов (\IT{jumptable}).

Может быть, 6 не самая подходящая константа для быстрого умножения, и может быть оно того и не стоит,
но вы поняли идею\footnote{В качестве упражнения, вы можете попробовать переработать этот код и избавиться
от таблицы переходов.
\myindex{x86!\Instructions!STOSB}
Пару инструкций тоже можно переписать так что они будут занимать 4 байта или 8.
1 байт тоже возможен (используя инструкцию \TT{STOSB}).}.

Так в прошлом делали с развернутыми циклами олд-скульные демомейкеры.
% TODO пример!

\subsection{Нужно ли использовать развернутые циклы?}
\myindex{Unrolled loop}

Развернутые циклы могут иметь преимущества если между \ac{RAM} и \ac{CPU} нет быстрой кэш-памяти и \ac{CPU},
чтобы прочитать код очередной
инструкции, должен загружать её каждый раз из \ac{RAM}.
Это случай современных маломощных \ac{MCU} и старых \ac{CPU}.

Развернутые циклы будут работать медленнее коротких циклов, если есть быстрый кэш между \ac{RAM} и \ac{CPU} и тело цикла
может поместиться в кэш и CPU будет загружать код оттуда не трогая \ac{RAM}.
Быстрые циклы это циклы у которых тело помещается в L1-кэш, но еще более быстрые циклы это достаточно маленькие,
чтобы поместиться в кэш микроопераций.

